/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025/2/16
 */
public class leetcode_35 {
    public static void main(String[] args) {
        int[] ints = {1, 3};
        System.out.println(searchInsert(ints, 2));
    }

    public static int searchInsert(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private static int binarySearch(int[] nums, int left, int right, int target) {
        // 二分查找循环
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出

            if (nums[mid] == target) {
                return mid;  // 找到目标值，返回索引
            } else if (nums[mid] > target) {
                right = mid - 1;  // 目标值在左半边
            } else {
                left = mid + 1;  // 目标值在右半边
            }
        }

        // 如果未找到目标值，left 即为目标值应该插入的位置
        return left;
    }
}
